package DataStructure.linkList;

/**
 * 234. 回文链表 https://leetcode.cn/problems/palindrome-linked-list
 * 题目简述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 */
public class IsPalindrome {

    /**
     * 思路一：递归。定义一个全局变量temp指向表头，递归head到表尾后尾递归回来的同时temp向表尾走，就可实现尾和头一一比较。
     */
    ListNode temp;
    public boolean isPalindrome(ListNode head) {
        temp = head;
        return check(head);
    }

    boolean check(ListNode head) {
        if (head == null)
            return true;
        //当check()递归到尾结点时 temp仍指向head，即比较head和尾结点的值，然后在回溯的过程中temp指向next 同时往中间走，实现尾和头一一比较
        boolean res = check(head.next) && temp.val==head.val;
        temp = temp.next;
        return res;
    }

    /**
     * 思路二：先用快慢指针找到链表中间节点，然后反转后半部分链表，最后再比较前后两部分链表
     */
    public boolean isPalindrome2(ListNode head) {
        ListNode mid = findMid(head);
        ListNode secondHalfRev = reverseList(mid);
        //比较前后两部分链表
        ListNode p1=head,p2=secondHalfRev;
        while(p1 != mid) {
            if(p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    //快慢指针寻找链表中间节点
    public ListNode findMid(ListNode head) {
        ListNode slow=head, fast=head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, next;
        while(head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
